
#include "stdafx.h"

#include <Runtime.Low/Pipeline/Pipeline.h>
#include <cstdio>

using namespace TTGLib::Pipeline;

typedef unsigned __int64 MyT;

struct Array {
	MyT *data;
	size_t size;
	int pos;
	__int64 key;
	Array(MyT *d, size_t s, int p, int k = 0): data(d), size(s), pos(p), key(k) {}
	Array(const Array &ar, size_t thr, __int64 order) {
		pos = ar.pos;
		if (order == 1) {
			data = ar.data;
			size = thr;
		} else {
			data = ar.data + thr;
			size = ar.size - thr;
		}
		key = ar.key * 2 + order;
	}
	bool operator < (const Array &ar) {
		return key < ar.key;
	}
};

struct SplittedArray: public Array {
	size_t threshold;
	SplittedArray(const Array &ar, size_t thr): Array(ar), threshold(thr) {}
};

size_t getPartition(Array input) {
	MyT mask = ((MyT)1) << input.pos;
	__int64 i = -1, j = input.size;
	while (i < j) {
		do {
			i++;
#ifdef _DEBUG
			for (int j = 0; j < 7; j++)
				printf("%c", *(((char *)(input.data+i)) + (6-j)));
			printf(" %lld\n", input.data[i] & mask);
#endif
		}while ((i < j) && !(input.data[i] & mask));
		do {
			j--;
		}while ((i < j) && (input.data[j] & mask));
		if (i < j) {
			MyT tmp = input.data[i];
			input.data[i] = input.data[j];
			input.data[j] = tmp;
		}
	}
	return i;
}

class MainCycleNode: public Node<Array, Array> {
	protected:
		static const int selfProcess = 1024000000;
		virtual void process(Array input) {
			if (input.pos >= 0 && input.size > 1) {
				__int64 har = input.size * (input.pos + 1);
/*				if (har > selfProcess) {
					size_t threshold = input.size / 2;
					sendNext(Array(input, threshold, 1));
					sendNext(Array(input, threshold, 2));
				} else {*/
#ifdef _DEBUG
					for (int i = 0; i < input.size; i++) {
						for (int j = 0; j < 7; j++)
							printf("%c", *(((char *)(input.data+i)) + (6-j)));
						printf("\n");
					}
#endif
					size_t threshold = getPartition(input);
#ifdef _DEBUG
					printf("%d\n", threshold);
#endif
					input.pos--;
					if (har < 327680) {
						if (threshold)
							process(Array(input, threshold, 1));
						if (input.size - threshold)
							process(Array(input, threshold, 2));
					} else {
						if (threshold)
							sendThis(Array(input, threshold, 1));
						if (input.size - threshold)
							sendThis(Array(input, threshold, 2));
					}
				//}
			}
		}
		long getDifficulty(Array input) {
			__int64 har = input.size * (input.pos + 1);
			/*if (input.pos < 0)
				return 0;
			if (har > selfProcess)
				return 1;
			if (har < 327680)
				return har;
			else
				return input.size;*/
			return ((~0) >> 1) - (har / 128); //dirty hack
		}
};

class SortPartNode: public Node<Array, SplittedArray> {
	protected:
		virtual void process(Array input) {
			sendNext(SplittedArray(input, getPartition(input)));
		}
		long getDifficulty(Array input) {
			return input.size;
		}
};

class ConcaterNode: public Node<SplittedArray, Array> {
	protected:
		virtual void chooseTaskData(std::list<SplittedArray> &dataset, std::vector<SplittedArray> &chosen) {
			dataset.sort();
			std::list<SplittedArray>::iterator it = dataset.begin(), it2 = dataset.begin();
			it2++;
			for (; it2 != dataset.end(); it2++) {
				if ((*it).key + 1 == (*it2).key && ((*it).key & 1)) {
					chosen.push_back((*it));
					chosen.push_back((*it2));
					return;
				}
				it = it2;
			}
		}
		virtual void process(std::vector<SplittedArray> input) {
			sort(input.begin(), input.end());
			size_t size = min(input[1].threshold, input[0].size - input[0].threshold);
			size_t bytes = sizeof(MyT)*size;
			if (bytes < 1048576) {
				if (bytes) {
					unsigned char tmp[1048576];
					memcpy(tmp, input[1].data, bytes);
					memcpy(input[1].data, input[0].data+input[0].threshold, bytes);
					memcpy(input[0].data+input[0].threshold, tmp, bytes);
				}
			} else {
				MyT *tmp = new MyT[size];
				memcpy(tmp, input[1].data, bytes);
				memcpy(input[1].data, input[0].data+input[0].threshold, bytes);
				memcpy(input[0].data+input[0].threshold, tmp, bytes);
				delete[] tmp;
			}
			input[0].pos--;
			input[1].pos--;
			if (input[0].threshold)
				sendNext(Array(input[0], input[0].threshold, 1));
			if (input[0].size - input[0].threshold)
				sendNext(Array(input[0], input[0].threshold, 2));
			if (input[1].threshold)
				sendNext(Array(input[1], input[1].threshold, 1));
			if (input[1].size - input[1].threshold)
				sendNext(Array(input[1], input[1].threshold, 2));
		}
		virtual void process(SplittedArray input) {
		}
		long getDifficulty(std::vector<SplittedArray> input) {
			sort(input.begin(), input.end());
			return min(input[1].threshold, input[0].size - input[0].threshold);
		}
};

int _tmain(int argc, _TCHAR* argv[])
{
	if (argc < 3) return 1;
	//for (size_t cnt = 1; cnt <= 4; cnt++)
	//for (int stp = 0; stp < 8; stp++)
	//{
	//	char in_buf[256];
	//	sprintf(in_buf, "input%dm.txt", stp * 10 + 2);
	//	argv[1] = in_buf;
	//	char out_buf[256];
	//	sprintf(out_buf, "output%dm.txt", stp * 10 + 2);
	//	argv[2] = out_buf;
	FILE *fin, *fout;
	fin = fopen(argv[1], "r");
	long count;
	fscanf(fin, "%ld", &count);
#ifdef _DEBUG
	printf("%ld\n", count);
#endif
	MyT *data = new MyT[count];
	for (long i = 0; i < count; i++) {
		unsigned char buf[10];
		fscanf(fin, "%s", buf);
		data[i] = 0;
		for (int j = 0; j < 7; j++)
			data[i] = data[i] + (((MyT)buf[j]) << ((6-j)*8));
	}
	fclose(fin);
	Array input(data, count, 55);
	Pipeline<Array, Array> mainPipe(NodeWrapper<Array, Array>(new MainCycleNode()) + NodeWrapper<Array, SplittedArray>(new SortPartNode()) + NodeWrapper<SplittedArray, Array>(new ConcaterNode()));
	double startTime = BaseServices::_Timer().getTimeD();
	mainPipe.start(input);
	//sort(input.data, input.data + input.size);
	double resultTime = (BaseServices::_Timer().getTimeD() - startTime) / 1000.0;
	printf("TIME = %lf\n", resultTime);
	fout = fopen(argv[2], "w");
	for (long i = 0; i < count; i++) {
		unsigned char buf[10] = {0};
		for (int j = 0; j < 7; j++)
			buf[j] = (data[i] >> ((6-j)*8)) & 0xFF;
		fprintf(fout, "%s\n", buf);
	}
	fclose(fout);
	SAFE_DELETE(data);
	//}
#ifdef _DEBUG
	char tmp[10];
	scanf("%s",tmp);
#endif
	return 0;
}
